// h

// 给定两个单词word1和word2，计算出将word1转为word2所使用的最少操作数
// 对一个单词可以进行以下三种操作
//   插入一个字符
//   删除一个字符
//   替换一个字符

// 解题思路，动态规划
// 1. 定义状态
//      dp[i][j] 为以i - 1为结尾的字符串word1转变为以j-1字结尾的字符串word2，所使用的最少操作次数
// 2. 状态转义方程
//      1.如果word1[i-1] = word2[j-1],则无需插入，删除，替换，dp[i][j]取源于以i-2结尾的字符串word1变为j-1结尾的字符串word2，即dp[i][j] = dp[i-1][j-1]
//      2.如果word1[i-1] !== word2[j-1],dp[i][j]取 源于以下三种情况中的最小情况：
//          1. word1在i-1位置上插入一个元素（等价于word2删除一个元素），最少操作次数依赖于以i-2结尾的字符串word1变为以j-1结尾的字符串word2，再加上插入需要的操作数1
//             即 d[i-1][j] + 1
//          2. word2在j-1位置上插入一个元素（等价于word1删除一个元素），最少操作次数依赖于以i-1结尾的字符串word1变为以j-2结尾的字符串word2，再加上插入需要的操作数1
//             即 dp[i][j-1] + 1
//          3. word1[i-1]替换为word2[j-1],最少操作次数依赖于以i-2结尾的字符串word1变为以j-2结尾的字符串word2，再加上替换的操作数1，
//             即 dp[i-1][j-1] + 1
// 3. 确定下边界条件
//      1. 当word1为空字符串，以j-1结尾的字符串word2需要删除j个字符才能和word1相同，即dp[0][j] = j
//      2. 当word2为空字符串，以i-1结尾的字符串word1需要删除i个字符才能和word2相同，即dp[i][0] = i

// 4. 最后递推求解，最终输出dp[size1][size2]为答案

function minDistance(word1, word2) {
    let size1 = word1.length
    let size2 = word2.length
    let dp = new Array(size1 + 1).fill(0).map(() => new Array(size2 + 1).fill(0))
    for (let i = 0; i <= size1; i++) {
        dp[i][0] = i        
    }
    for (let i = 0; i <= size2; i++) {
        dp[0][i] = i        
    }
    for (let i = 1; i <= size1; i++) {
        for (let j = 1; j <= size2; j++) {
            if (word1[i - 1] === word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1]
            } else {
                dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
            }
        }
    }
    return dp[size1][size2]
}

let word1 = "horse", word2 = "ros"
console.log(minDistance(word1, word2))